use std::cell::RefCell;
use std::fmt;
use std::rc::Rc;

// 1. 活动选择问题 —— 递归贪心算法
pub fn recursive_activity_selector(s: &Vec<u8>, f: &Vec<u8>, k: usize, n: usize) -> Vec<usize> {
    let mut m = k + 1;
    while m <= n && s[m] < f[k] {
        m += 1;
    }
    let mut temp = vec![];
    if m <= n {
        temp.push(m);
        temp.append(&mut recursive_activity_selector(s, f, m, n));
    }
    temp
}

// 1.2 迭代贪心算法
pub fn greedy_activity_selector(s: &Vec<u8>, f: &Vec<u8>) -> Vec<usize> {
    let n = s.len();
    let mut a = vec![1];
    let mut k = 0;
    for m in 1..n {
        if s[m] >= f[k] {
            a.push(m + 1);
            k = m;
        }
    }
    a
}

// 2. 赫夫曼编码
#[derive(Debug, Clone)]
pub struct HuffmanNode {
    left: Option<Rc<RefCell<HuffmanNode>>>,
    right: Option<Rc<RefCell<HuffmanNode>>>,
    freq: u32,
}

impl fmt::Display for HuffmanNode {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        let mut node_list: Vec<Option<Rc<RefCell<HuffmanNode>>>> = Vec::new();
        let mut node_list_temp: Vec<Option<Rc<RefCell<HuffmanNode>>>> = Vec::new();
        node_list.push(Some(Rc::new(RefCell::new(self.clone()))));
        while !node_list.is_empty() {
            node_list_temp.clear();
            for node in node_list.iter() {
                if let Some(l) = node {
                    let temp = l.as_ref().borrow();
                    print!("{} --- ", temp.fre());
                    node_list_temp.push(temp.left.clone());
                    node_list_temp.push(temp.right.clone());
                } else {
                    print!("Nul --- ");
                }
            }
            println!("|");
            node_list = node_list_temp.clone();
        }
        write!(f, "Over")
    }
}
impl HuffmanNode {
    pub fn build(v: u32) -> Self {
        HuffmanNode {
            left: None,
            right: None,
            freq: v,
        }
    }
    pub fn fre(&self) -> u32 {
        self.freq.clone()
    }
}

pub fn huffman_min_headify(a: &mut Vec<HuffmanNode>, i: usize, len: usize) {
    let l: usize = (i << 1) + 1;
    let r: usize = (i + 1) << 1;
    let mut leastest = i;
    if l < len && a[l].fre() < a[i].fre() {
        leastest = l;
    }
    if r < len && a[r].fre() < a[leastest].fre() {
        leastest = r;
    }
    if leastest != i {
        a.swap(i, leastest);
        huffman_min_headify(a, leastest, len);
    } else {
        return;
    }
}

pub fn huffman_build_min_heap(a: &mut Vec<HuffmanNode>) {
    let len = a.len();
    for i in (0..=(len >> 1)).rev() {
        huffman_min_headify(a, i, len);
    }
}

pub fn huffman_heap_extract_min(a: &mut Vec<HuffmanNode>) -> Option<HuffmanNode> {
    if a.len() < 1 {
        return None;
    }
    let max = a[0].clone();
    a[0] = a.last().unwrap().clone();
    a.remove(a.len() - 1);
    huffman_min_headify(a, 0, a.len());
    Some(max)
}

pub fn huffman_heap_increase_key(a: &mut Vec<HuffmanNode>, i: usize, key: HuffmanNode) {
    if key.fre() < a[i].fre() {
        panic!("new key is smaller than current key");
    }
    a[i].freq = key.fre();
    let mut i = i;
    while i > 0 && a[i].fre() > a[i >> 1].fre() {
        a.swap(i, i >> 1);
        i >>= 1;
    }
}

pub fn huffman_max_heap_insert(a: &mut Vec<HuffmanNode>, key: HuffmanNode) {
    a.push(key.clone());
    huffman_heap_increase_key(a, a.len() - 1, key);
}

pub fn huffman(q: &mut Vec<HuffmanNode>) -> Option<HuffmanNode> {
    let n = q.len();
    huffman_build_min_heap(q);
    for _ in 0..(n - 1) {
        let mut z = HuffmanNode::build(q[0].freq.clone());
        let mut temp = 0;
        if let Some(x) = huffman_heap_extract_min(q) {
            temp += x.fre();
            z.left = Some(Rc::new(RefCell::new(x)));
        }
        if let Some(y) = huffman_heap_extract_min(q) {
            temp += y.fre();
            z.right = Some(Rc::new(RefCell::new(y)));
        }
        z.freq = temp;
        huffman_max_heap_insert(q, z)
    }
    huffman_heap_extract_min(q)
}
